/*
 * Grafo.cpp
 *
 *  Created on: Jan 24, 2014
 *      Author: ik
 */

#include <cstring>
#include <fstream>
#include <cstdlib>
#include <Grafo.h>

using namespace std;

//constructor
DiGrafo::DiGrafo(int n)
{
	initialize(n);
}

//constructor
DiGrafo::DiGrafo(DiGrafo& otro) : _n(otro._n)
{
	_vertices = new VertexSet(_n);
	_vertices->copyAll(*(otro._vertices));
	_arista = new VertexSet*[_n];
	for (int i = 0; i < _n; i++)
	{
		if (otro.isVertice(i))
		{
			_arista[i] = new VertexSet(_n);
			_arista[i]->copyAll(*(otro._arista[i]));
		}
		else
			_arista[i] = 0;
	}
	_enumerablesI = new Lista(_n);
}

//constructor
DiGrafo::DiGrafo(DiGrafo& otro, Lista& orden) : DiGrafo(otro._n)
{
//	initialize(otro._n);

	int maporden[_n];
	for (int v = 0; v < orden.cantidad(); v++)
		maporden[orden[v]] = v;
	for (int i = 0; i < orden.cantidad(); i++) {
		int v = orden[i];
		addVertice(i);

		for (VertexSetIterator w = otro.vecinos(v).begin(); w != otro.vecinos(v).end(); ++w) {
			int j = maporden[*w];
			addVertice(j);
			addArco(i, j);
		}
	}
}

Grafo::Grafo(int n) : DiGrafo(n)
{

}

Grafo::Grafo(Grafo &otro) : DiGrafo(otro)
{

}

Grafo::Grafo(Grafo &otro, Lista& orden) : DiGrafo(otro, orden)
{

}

//constructor
DiGrafo::DiGrafo(string archivoDIMACS)
{
	string line;
	ifstream file(archivoDIMACS.c_str());
	if (file.is_open())
	{
		while ( getline (file,line) )
		{
			if (line.empty())
				continue;

			if (line[0] == 'p')
			{
				int pos = line.rfind(" ");
				pos = line.substr(0, pos).rfind(" ")+1;
				int n = atoi(line.substr(pos, line.length() - pos).c_str());
				initialize(n);
			}

			if (line[0] == 'e')
			{
				int posI = line.find(" ")+1;
				int posJ = line.rfind(" ")+1;

				int i = atoi(line.substr(posI , posJ - posI).c_str())-1;
				int j = atoi(line.substr(posJ , line.length() - posJ).c_str())-1;
				addVertice(i);
				addVertice(j);
				addArco(i,j);
				addArco(j,i);
			}
		}
		file.close();
	}
}

//constructor
Grafo::Grafo(string archivoDIMACS) : DiGrafo(archivoDIMACS)
{
}

Grafo::~Grafo()
{

}

void DiGrafo::haceIncambiable() {
	VertexSet * aux;
	aux = _vertices->turnToUnmodifiable();
	delete _vertices;
	_vertices = aux;

	_vertices->lista(*_enumerablesI);
	for (int i = 0; i < _enumerablesI->size(); i++) {
		aux = _arista[i]->turnToUnmodifiable();
		delete _arista[i];
		_arista[i] = aux;
	}
}

/*!
 * \brief inicializa, para no repetir código en el constructor.
 *
 * Nota: En C++, los constructores no se pueden llamar unos a otros.
 * Más aún, el compilador requiere una copia del código manuscrita en cuero de oveja, para funcionar.
 */
void DiGrafo::initialize(int n)
{
	_n = n;
	_vertices = new VertexSet(_n);
	_arista = new VertexSet*[_n];
	memset(_arista, 0, _n*sizeof(VertexSet *));
	_enumerablesI = new Lista(_n);
	_working = new VertexSet(_n);

	_compGradosCrecientes._g = this;
	_compGradosDecrecientes._g = this;
}

//destructor
DiGrafo::~DiGrafo()
{
	_enumerablesI->clear();
	_vertices->lista(*_enumerablesI);
	for (int i = 0; i < _enumerablesI->cantidad(); i++)
		delete _arista[(*_enumerablesI)[i]];

	delete [] _arista;
	delete _vertices;
	delete _enumerablesI;
	delete _working;
}

void DiGrafo::turnToComp()
{
	for (int i = 0; i < _n; i++) {
		if (isVertice(i))
		{
			_arista[i]->turnToCompl();
			_arista[i]->remove(i);
		}
		else
		{
			addVertice(i);
			_arista[i]->addAll();
			_arista[i]->remove(i);
		}
	}
}

void DiGrafo::copy(DiGrafo& otro)
{
	for (int i = 0; i < _n; i++)
		if (otro.isVertice(i))
		{
			addVertice(i);
			_arista[i]->copyAll(*otro._arista[i]);
		}
		else if (isVertice(i))
		{
			delete _arista[i];
			_arista[i] = 0;
			_vertices->remove(i);
		}
}

void DiGrafo::copySubgrafo(const DiGrafo& otro, const VertexSet& subgrafo)
{
	for (int i = 0; i < _n; i++)
		if (otro.isVertice(i) && subgrafo.contains(i))
		{
			addVertice(i);
			_arista[i]->copyAll(*otro._arista[i]);
			_arista[i]->retainAll(subgrafo);
		}
		else if (isVertice(i))
		{
			delete _arista[i];
			_arista[i] = 0;
			_vertices->remove(i);
		}
}

bool DiGrafo::containsAsSubgrafo(const DiGrafo& otro, const VertexSet& subgrafo)
{
	bool ret = true;
	_enumerablesI->clear();
	subgrafo.lista(*_enumerablesI);
	for (int i = 0; ret && i < _enumerablesI->cantidad(); i++)
		ret = (isVertice((*_enumerablesI)[i]) && _arista[(*_enumerablesI)[i]]->containsInter(subgrafo, otro.vecinos((*_enumerablesI)[i])));
	return ret;
}

bool Grafo::isClique(const VertexSet& c) const
{
	_working->copyAll(c);
	_enumerablesI->clear();
	_working->lista(*_enumerablesI);
	bool esClique = true;
	for (int i = 0; i < _enumerablesI->cantidad() && esClique; i++)
	{
		int ei = (*_enumerablesI)[i];
		_working->remove(ei);
		esClique = _working->isSubsetOf(vecinos(ei));
		_working->add(ei);
	}

	return esClique;
}

bool Grafo::isStable(const VertexSet& c) const
{
	_working->copyAll(c);
	VertexSetIterator i = _working->begin();
	for (; i != _working->end() && _working->isDisjoint(vecinos(*i)); ++i);
	return i == _working->end();
}

bool Grafo::isInducedTree(const VertexSet& c) const
{
	VertexSet mark(_n);
	_enumerablesI->clear();
	(*_enumerablesI) += c.least();
	int head = 0;
	while (head < _enumerablesI->cantidad() && !mark.contains((*_enumerablesI)[head]))
	{
		_working->copyAll(c);
		_working->retainAll(vecinos((*_enumerablesI)[head]));
		_working->removeAll(mark);
		for (VertexSetIterator i = _working->begin(); i != _working->end(); ++i)
			(*_enumerablesI) += *i;
		mark.add((*_enumerablesI)[head++]);
	}
	return c.isSubsetOf(mark);
}

void DiGrafo::clear()
{
	_enumerablesI->clear();
	_vertices->lista(*_enumerablesI);
	for (int i = 0; i < _enumerablesI->cantidad(); i++)
		delete _arista[(*_enumerablesI)[i]];
	_vertices->removeAll();
}

void DiGrafo::crecienteGrado(Lista& orden) {
	sort(orden.begin(), orden.end(), _compGradosCrecientes);
}

void DiGrafo::decrecienteGrado(Lista& orden) {
	sort(orden.begin(), orden.end(), _compGradosDecrecientes);
}
